from functools import cache
import sys
from typing import List

# 01背包问题 ==》 子问题： 当前元素 选 or 不选 的问题

# 记忆化搜索+ 剪枝
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sys.setrecursionlimit(10**9)
        n=len(nums)
        total=sum(nums)
        # 总和是奇数，则无法分割
        if total%2==1:
            return False

        # 对于当前元素 选 or 不选 各自加到一个数组里面
        @cache
        def dfs(i,cnt1):
            # 只有两数相等 且 遍历完最后一个元素时，结果为True
            if cnt1==total//2 and i==n:
                return True
            if i>=n:
                return False
            # 选 or 不选
            return dfs(i+1,cnt1+nums[i]) or dfs(i+1,cnt1)

        return dfs(0,0)

